02 Grej

Грејови кодови су сачињени од ниски нула и јединица и имају особину да се свака два суседна елемента у коду разликују на тачно једној позицији. Исто важи и за први и последњи елемент. На пример,

0.  000
1.  001
2.  011
3.  010
4.  110
5.  111
6.  101
7.  100

Грејов код у ком су ниске дужине n + 1 се добија рекурзивно. Прва половина кода се добија дописивањем цифре 0 на почетак сваке ниске Грејовог кода дужине n, а друга половина дописивањем цифре 1 на почетак сваке ниске Грејовог кода дужине n, при чему се у другом случају ниске ређају у обратном редоследу. Грејов код дужине 0 садржи само празну ниску. Заиста, претходни Грејов код је конструисан баш на овај начин.

0 00
0 01
0 10
0 11

1 11
1 10
1 01
1 00

Написати програм који одређује редни број дате ниске унутар овако конструисаног Грејовог кода.

Улаз

Са стандардног улаза се учитава ниска која се састоји само од карактера 0 и 1 и дужина јој је n (1 ≤ n ≤ 20).

Излаз

На стандардни излаз исписати њену позицију унутар Грејовог кода одговарајуће дужине.

Пример 1

Улаз

111

Излаз

5

Пример 2

Улаз

1000

Излаз

15